/**
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 * 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * @param s 
 */
 const longestValidParentheses = (s: string): number => {
    const len = s.length;

    // 空串
    if (len === 0) return 0

    // 存放左括号的栈顶
    const stack: number[] = []

    // 存放第一个索引
    stack.push(-1); // 用来保证最后一个右括号也能匹配 e.g: (())  遇到最后一个右括号的时候, 如果没有-1, 此时最后一个右括号就匹配不到了

    let max = 0
    for (let i = 0; i < len; i++) {
        if (s[i] === '(') {
            // 是左括号, 将下标放入栈中
            stack.push(i)
        } else {
            // 弹出栈顶
            stack.pop();

            if (stack.length === 0) {
                // 栈为空, 将该右括号的下标放入栈中, 为了后面继续匹配完整的括号做准备
                stack.push(i)
            } else {
                max = Math.max(max, i - stack[stack.length - 1])
            }
        }
    }
    return max
};


// error
const longestValidParentheses2 = (s: string): number => {
    // "()()((()"
    const len = s.length;

    // 空串
    if (len === 0) return 0

    // 存放左括号的栈顶
    const stack: string[] = []
    let max = 0,
        preMax = 0, // 总共匹配到的有效的括号长度
        prevI = -1
    for (let i = 0; i < len; i++) {
        const char = s[i]
        if (char === '(' ) {
            // 是左括号, 并且不是最后一项 入栈
            stack.push(char)
        } else {
            // 是右括号但是栈为空, 说明这个右括号不匹配
            if (stack.length === 0) { // 将prevMax置为0
                preMax = 0
                continue
            }

            // 栈顶是左括号, 长度加2
            if (stack.pop() === '(') {
                preMax += 2;
                if (max === 0)max = 2 // 匹配到了, max至少是2

                if (prevI !== -1 && ((s[prevI] == ')' && i - prevI === 1) || (s[i - 1] === '(' && i - prevI === 2))) { // 上一个是)并且间隔为1 || 上一个是(但是间隔是2
                    max = Math.max(preMax, max)
                }
                prevI = i
            }
        }
    }
    return max
};

// "()((())()"
// console.log(longestValidParentheses("()(())")) // 6
// console.log(longestValidParentheses('(()')) // 2
// console.log(longestValidParentheses('')) // 0
// console.log(longestValidParentheses("(()()")) // 4
// console.log(longestValidParentheses(")()())")) // 4
// console.log(longestValidParentheses("(((()))")) // 6
// console.log(longestValidParentheses(")()())()()(")) // 4
console.log(longestValidParentheses("(()))())(")) // 4
// -1
// -1 0
// -1 0 1
// -1 0
// -1
// 4
// 4 5
// 4
// 7 8

// ()()  || (())